/*
 * @lc app=leetcode.cn id=198 lang=cpp
 *
 * [198] 打家劫舍
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> dp;
    int rob(vector<int>& nums) {
        
        dp = vector<int>(nums.size() + 1, 0);

        dp[1] = nums[0];
        if(nums.size() > 1) dp[2] = max(nums[0], nums[1]);
        for(int k = 3; k <= nums.size(); k++)
        {
            dp[k] = max(dp[k-2] + nums[k-1], dp[k-1]);
        }
        return dp[nums.size()];
    }
};
// @lc code=end

